Over the past decade, semiconductor process technology has rapidly progressed to permit ever more complex systems to be integrated onto a single monolithic chip. As a result, system designers have increased their demand for computer aided design (CAD) tools to automate the design process and thereby reduce the time necessary to implement their system designs in silicon.
What was once a "bottom-up" design process, beginning from the circuit and gate level and working toward the system level, has become an increasingly "top-down" process, whereby the system designer designs a system at the abstract or behavioral level and works down toward its implementation on the circuit and gate level.
A number of factors have been responsible for the move to a "top-down" approach. First, the availability of standard cell libraries, gate-arrays and ASIC technology has provided the system designer with generic semiconductor building blocks with which to implement system designs. Further, CAD tools such as System 1076 by Mentor are able to create hardware descriptions of systems designs using a standard language such as VHDL (Very High-Scale Integrated Circuit Hardware Description Logic). A system represented in VHDL can then be fed into a synthesis tool, which converts the VHDL representation into an actual circuit block implementation for a given semiconductor technology. An example of a synthesis tool is Design Compiler by Synopsys.
Before a system design can be implemented in silicon, its behavior must be verified as that which is desired by the designer. CAD tools such as System 1076 by Mentor simulate the system once it has been converted to a VHDL representation to verify logical behavior and/or timing behavior of the system. Simulators such as System 1076 are event-driven simulators. They execute models of the functions comprising the system by dynamically scheduling the execution of those functions at run-time.
Event driven simulators are extremely slow and resource intensive, however, particularly for very complex systems. Because they do not know, a priori, the order in which particular functional blocks will be executed, they must maintain an event queue to schedule the execution of blocks in the future. This dynamic schedule can change at any time by the occurrence of unexpected intervening events, and must therefore be constantly updated during execution. Further, if the input to a particular functional block is fired (i.e. the block which is its output is executed), the simulator will execute the block even if the result of that execution is only an intermediate result with no impact on the overall system. Finally, the execution schedule which is ultimately simulated will not be the most optimal.
For some time, those skilled in the art have known that digital signal processing systems can be represented by signal flow diagrams. A technical article which discusses in detail background information regarding the representation of systems using synchronous data flow diagrams is E. A. Lee and D. G. Messerschmitt, "Static Scheduling of Synchronous Data Flow Programs for Digital Signal Processing," IEEE Transactions or Computers, 24-35 (1987), which is by this statement incorporated herein by reference. DSP systems are particularly amenable to this representation because the inherent nature of the algorithms which are employed in DSP systems require signals to flow from one block to another unidirectionally, and only one source for data flow is permitted per data path. Those skilled in the art have also known that such systems may be statically scheduled such that a priori, the system designer knows precisely in what order at any point in time when a particular block in the system will be executed. A method for optimizing the static schedule for a signal flow diagram is disclosed in the commonly owned U.S. patent application Ser. No. 08/053,607, which is by this statement incorporated herein by reference.
Those skilled in the art also have known that the data flow behavior of these systems may be simulated according to the static schedule optimized by the designer. Because such a simulator requires no event queue, and because the simulator will not execute system blocks unnecessarily, a statically scheduled simulation can run significantly faster than event driven simulators.
Up until the present, those of ordinary skill in the art and beyond had believed that static scheduling of systems which employ multiple sources to drive the same data flow path, such as the case of a bidirectional or multiplexed bus, was not possible. The common wisdom has been that there is no way to resolve contention between two drivers on the same path in the a priori manner required of a statically scheduled simulator. Thus, despite the demand for faster simulation tools for developing systems other than those having a DSP application, statically scheduled simulation has not heretofore been extended to the general case of a system which employs multiple drivers and/or bidirectional data flow.